package 回溯算法;

/**
 * @Author: biubiu0002
 * @Date: 2021-09-16 21:24
 **/
public class 单词搜索 {
    public static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private int row, col;


    public static void main(String[] args) {

    }

    public boolean exist(char[][] board, String word) {
        row = board.length;
        col = board[0].length;
        boolean[][] isUsed = new boolean[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                //回溯
                if (backtrace(board, i, j, word, 0, isUsed)) {
                    return true;
                }

//                if(board[i][j]==word.charAt(0)){
//                    //做选择
//                    isUsed[i][j]= true;
//
////                    return check(board,isUsed,word,0);
//                }
            }

        }
        return false;

    }

    public boolean backtrace(char[][] board, int r, int c, String word, int curlen, boolean[][] isUsed) {
        //base case
        if (curlen == word.length()) {
            return true;
        }
        if (r < 0 || r >= row || c < 0 || c >= col
                || board[r][c] != word.charAt(curlen)
                || isUsed[r][c]) {
            return false;
        }
        //做选择
        isUsed[r][c] = true;
        for(int[]d : DIRECTIONS){
            //下一层
            if(backtrace(board,r+d[0],c+d[1],word,curlen+1,isUsed)){
                return true;
            }


        }
        //撤销选择
        isUsed[r][c]=false;
        return false;



    }


}
